package Leetcode;

import java.util.ArrayList;
import java.util.Deque;
import java.util.LinkedList;
import java.util.List;

// 递归
class Solution145_1 {
    List<Integer> list = new ArrayList<>();

    public List<Integer> postorderTraversal(TreeNode root) {
        if (root == null)
            return list;
        postorder(root);
        return list;
    }

    public void postorder(TreeNode root) {
        if (root.left != null)
            postorder(root.left);
        if (root.right != null)
            postorder(root.right);
        list.add(root.val);
    }
}

// 迭代
class Solution145_2 {
    public List<Integer> postorderTraversal(TreeNode root) {
        Deque<TreeNode> stack1 = new LinkedList<>();
        Deque<Integer> stack2 = new LinkedList<>();
        List<Integer> list = new ArrayList<>();
        if (root == null)
            return list;
        stack1.push(root);
        // 按根右左的顺序入栈
        while (!stack1.isEmpty()) {
            TreeNode node = stack1.pop();
            stack2.push(node.val);
            if (node.left != null)
                stack1.push(node.left);
            if (node.right != null)
                stack1.push(node.right);
        }
        while (!stack2.isEmpty()) {
            list.add(stack2.pop());
        }
        return list;
    }
}

// Morris算法
class Solution145_3 {
    List<Integer> list = new ArrayList<>();

    public List<Integer> postorderTraversal(TreeNode root) {
        TreeNode currentRoot = root; // 当前开始遍历的结点
        TreeNode cur = null; // 记录当前结点的左子树

        while (currentRoot != null) {
            cur = currentRoot.left;
            // 如果当前结点有左子树
            if (cur != null) {
                // 左子树的右节点不为空且还没有与根结点建立连接
                while (cur.right != null && cur.right != currentRoot)
                    cur = cur.right;
                // 此时要么cur.right==null,要么cur.right==currentRoot
                // 这个时候如果最右侧这个节点的右指针没有指向根结点，创建连接然后往下一个左子树的根结点进行连接操作。
                if (cur.right == null) {
                    cur.right = currentRoot;
                    currentRoot = currentRoot.left;
                    continue;
                }
                // 当左子树的最右侧节点有指向根结点，此时说明我们已经回到了根结点并重复了之前的操作，
                // 同时在回到根结点的时候我们应该已经处理完左子树的最右侧节点了，把路断开。
                else {
                    cur.right = null;
                    print(currentRoot.left);
                }
            } // if
              // 不是回到上一个根结点，而是到当前root的右子树
            currentRoot = currentRoot.right;
        } // while
        print(root);

        return list;
    }

    public void print(TreeNode root) {
        Deque<Integer> stack = new LinkedList<>();
        while (root != null) {
            stack.push(root.val);
            root = root.right;
        }
        while (!stack.isEmpty()) {
            list.add(stack.pop());
        }
    }

}